﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <locale>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numProject int整型
     * @param groups int整型vector<vector<>>
     * @return int整型vector
     */
    vector<int> findOrder(int numProject, vector<vector<int> >& groups)
    {
        //拓扑排序
        vector<vector<int>> edges(numProject);//存储边
        vector<int> in(numProject);//存储入度

        for (auto v : groups)//建图
        {
            edges[v[1]].push_back(v[0]);//先完成v[1]，再完成v[0]
            in[v[0]]++;//v[0]的入度加1
        }

        queue<int> q;

        for (int i = 0; i < numProject; ++i)//入度为0的存入队列
        {
            if (!in[i])
            {
                q.push(i);
            }
        }

        vector<int> result;
        while (!q.empty())
        {
            int pro = q.front();
            q.pop();
            result.push_back(pro);
            for (auto e : edges[pro])//有课程学了，更新依赖关系
            {
                --in[e];
                if (!in[e])//该课程所有的依赖已经学习了
                {
                    q.push(e);
                }
            }
        }

        if (result.size() == numProject)
            return result;
        else
            return {};
    }
};

/*
体育课共有numProject个考核项目，编号为
0到numProject−1，考核中每两个项目被划分为一组得到分组数组groupsi，
现规定若想完成项目groupsi[0]，必须先完成groupsi[1]。保证所有分组互不相同，
若分组情况能顺利完成考核，请返回任意的一个完成顺序,否则返回空数组 。
数据范围：1≤numProject≤2000，1≤groupsi.length≤numProject∗(numProject−1)

 示例1
输入：
3,[[2,1]]
返回值：
[1,2,0]
说明：
要先完成1号项目，再完成2号项目，而0号项目不受约束，故可以以1 2 0的顺序完成项目。
*/

